package io.adrainty.algorithm.mars;

/**
 * 小U的最大连续移动次数问题
 * @link <a href="https://www.marscode.cn/practice/364l85wv6oo6lq?problem_id=7424418560929792044">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/11/29 下午1:35
 */
public class Solution018 {

    private Solution018() {}

    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    /**
     * 小U决定在一个 m * n 的地图上行走。地图中的每个位置都有一个高度，表示地形的高低。小U可以在满足以下条件的情况下移动
     * 1.只能上坡或者下坡，不能走到高度相同的点。
     * 2.移动时必须交替进行：上坡后必须下坡，下坡后必须上坡，不能连续上坡或下坡。
     * 3.每个位置只能经过一次，不能重复行走。
     * @param m 行
     * @param n 列
     * @param a 地图
     * @return 小U能走过的最大连续位置数量。
     */
    public static int solution(int m, int n, int[][] a) {
        // write code here

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean[][] visited = new boolean[m][n];
                // List<Integer> route = new ArrayList<>();
                // route.add(a[i][j]);
                // 从[i, j]开始搜索
                // System.out.printf("从[%d][%d]开始查找: \n", i, j);
                // int res = dfs(m, n, i, j, a, visited, -1, 0, route);
                int res = dfs(m, n, i, j, a, visited, -1, 0);
                res = Math.max(0, res - 1);
                // System.out.println("当前结果：" + res);
                ans = Math.max(ans, res);
            }
        }

        return ans;
    }

    /**
     * 搜索[i, j]开始可以到达的最大连续位置数量
     * @param m 最大行
     * @param n 最大列
     * @param i 当前行
     * @param j 当前列
     * @param a 地图
     * @param preValue 上一次访问的值
     * @param visited 访问数组
     * @param attr 到当前位置的方向 向上 1 or 向下 -1 如果为0 则表示为第一个起点
     * @return 最大连续位置数量
     */
    private static int dfs(int m, int n, int i, int j, int[][] a, boolean[][] visited, int preValue, int attr) {
        // 边界条件 超过边界 或者已访问
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
            // System.out.println("111 当前路径: " + route + " 当前结果: " + route.size());
            return 0;
        }
        int curValue = a[i][j];
        if (preValue == curValue) return 0;

        int currentAttr = 0;
        if (preValue != -1) {   // 不是第一次访问
            currentAttr = Integer.compare(curValue, preValue);
            // 不满足上下坡条件
            // 相乘等于0 说明相等, 大于0 说明方向相同
            if (attr != 0 && currentAttr * attr >= 0) {
                // System.out.println("222 当前路径: " + route + " 当前结果: " + route.size());
                return 0;
            }
        }

        // 记录该点已经访问过
        visited[i][j] = true;
        // route.add(a[i][j]);

        int ans = 0;
        for (int[] direction : DIRECTIONS) {
            int x = i + direction[0];
            int y = j + direction[1];
            // int cur = 1 + dfs(m, n, x, y, a, visited, curValue, currentAttr, route);
            int cur = 1 + dfs(m, n, x, y, a, visited, curValue, currentAttr);
            ans = Math.max(ans, cur);
        }

        // 清除该点访问记录, 进入下一次循环
        visited[i][j] = false;
        // route.remove(route.size() - 1);
        return ans;
    }

}
